//图的邻接矩阵结构体实现，空间复杂度：O(|V|^2)

#define MaxVertexNum 100  //顶点数目的最大值
#define MAX_WEIGHT 0Xffff //边的最大权重
typedef int VertexType;   //顶点数据类型
typedef int EdgeType;     //带权图中边上权值的数据类型 (非带权图的边的权值为1)

typedef struct //邻接矩阵结构体
{
    bool DirStatue = false;                    // false代表该图为无向图；true代表该图为有向图
    VertexType Vex[MaxVertexNum];              //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵(边表)【二维数组】
    int vexnum, arcnum;                        //图的当前顶点数和弧数
} MGraph;                                      // MGraph是以邻接矩阵存储的图类型

void Init(MGraph &G) //初始化图G
{
    for (int i = 0; i < MaxVertexNum; ++i) //遍历邻接矩阵
    {
        G.Vex[i] = i; //顺便在一重循环里，把图G的顶点对应的序号规定一下，默认从0开始一直到MaxVertexNum
        for (int j = 0; j < MaxVertexNum; ++j)
        {
            if (i == j) //使邻接矩阵的主对角线都为0
                G.Edge[i][j] = 0;
            else //使非主对角线的元素都为最大值(无穷)
                G.Edge[i][j] = MAX_WEIGHT;
        }
    }
    return;
}

inline int find(MGraph G, VertexType x) //寻找顶点x在顶点表中的位置(序号)；若x不存在，则返回-1
{
    for (int i = 0; i < MaxVertexNum; ++i)
        if (G.Vex[i] == x)
            return i;
    return -1;
}

//若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边
bool AddEdge(MGraph &G, VertexType x, VertexType y, int weight = 1)
{
    int i = find(G, x);         //寻找顶点x在顶点表中的位置(顶点号)
    int j = find(G, y);         //寻找顶点y在顶点表中的位置(顶点号)
    if (G.Edge[i][j] == weight) //如果该边存在，则返回false退出
        return false;
    if (G.DirStatue) //若该图为有向图
        G.Edge[i][j] = weight;
    else //若该图为无向图
    {
        G.Edge[i][j] = weight;
        G.Edge[j][i] = weight;
    }
    return true;
}

//求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1
int FirstNeighbor(MGraph G, VertexType x)
{
    int i = find(G, x); //寻找顶点x在顶点表中的位置(顶点号)
    if (i == -1)        //若x不存在，则返回-1
        return -1;
    for (int j = 0; j < MaxVertexNum; ++j) //遍历顶点x所在的那一行，寻找第一个邻接点的顶点号
    {
        if (G.Edge[i][j] != 0 && G.Edge[i][j] != MAX_WEIGHT) //权重不为0，也不为无穷
            return j;
    }
    return -1;
}

//假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1
int NextNeighbor(MGraph G, VertexType x, VertexType y)
{
    int i = find(G, x); //寻找顶点x在顶点表中的位置(顶点号)
    if (i == -1)        //若x不存在，则返回-1
        return -1;
    int j = find(G, y);              //寻找顶点y在顶点表中的位置(顶点号)
    for (++j; j < MaxVertexNum; ++j) //从y所在位置的下一列开始遍历x那一行，寻找下一个邻接点的顶点号
    {
        if (G.Edge[i][j] != 0 && G.Edge[i][j] != MAX_WEIGHT) //若顶点y不是边表中的最后一个顶点，则返回后一个顶点
            return j;
    }
    return -1;
}